/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q0160.java
 * @Author : WangRuoyu
 * @Date 2022/12/26 17:35
 */

package leetcode;

import util.LinkList;
import util.ListNode;

import java.util.HashSet;

public class Q0160 {

    /*** 哈希表 ***/
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//
//        HashSet<ListNode> set = new HashSet<>();
//
//        while (headA != null) {
//            set.add(headA);
//            headA = headA.next;
//        }
//
//        while (headB != null) {
//            if (set.contains(headB)) {
//                return headB;
//            }
//            headB = headB.next;
//        }
//
//        return null;
//    }

    /*** 两次遍历 ***/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if ((headA == null) || (headB == null)) {
            return null;
        }
        ListNode ha = headA;
        ListNode hb = headB;
        while (ha != hb) {
            if (ha == null) {
                ha = headB;
            } else {
                ha = ha.next;
            }
            if (hb == null) {
                hb = headA;
            } else {
                hb = hb.next;
            }
        }
        return ha;
    }

    public static void main(String[] args) {
        Q0160 sl = new Q0160();
        ListNode heada = LinkList.createList(new int[]{1, 2, 3});
        ListNode headb = LinkList.createList(new int[]{1, 2, 3});
        ListNode p = new ListNode(4);
        heada.next.next.next = p;
        headb.next.next.next = p;
        System.out.println(sl.getIntersectionNode(heada, headb));
    }
}